/**
 * @version Create on 2012-11-11
 * @author Yinzi Chen
 */

public class MinimumPathSum {

	public int minPathSum(int[][] grid) {
		int n = grid.length;
		if (n == 0)
			return 0;
		int m = grid[0].length;
		if (m == 0)
			return 0;
		int[][] dp = new int[n + 1][m + 1];
		for (int i = 0; i <= n; ++i)
			for (int j = 0; j <= m; ++j)
				dp[i][j] = Integer.MAX_VALUE;
		dp[1][1] = grid[0][0];
		for (int i = 1; i <= n; ++i)
			for (int j = 1; j <= m; ++j) {
				if (dp[i - 1][j] != Integer.MAX_VALUE) {
					dp[i][j] = Math.min(dp[i][j], dp[i - 1][j]
							+ grid[i - 1][j - 1]);
				}
				if (dp[i][j - 1] != Integer.MAX_VALUE) {
					dp[i][j] = Math.min(dp[i][j], dp[i][j - 1]
							+ grid[i - 1][j - 1]);
				}
			}
		return dp[n][m];
	}

	public static void main(String[] args) {

	}

}
